package tree;

import java.util.Stack;

public class BinaryTree {
    private char data;
    private BinaryTree lTree;
    private BinaryTree rTree;

    /**
     * 使用括号字符串来创建二叉树，例如 A(B(C,),D)
     * 
     * @param str 括号形式表示的二叉树串
     */
    public BinaryTree(String str) {
        // 使用栈来处理括号配对
        Stack<BinaryTree> stack = new Stack<>();
        // 将输入字符串转换为字符数组
        char[] charArray = str.toCharArray();
        // 构建根节点
        this.data = charArray[0];
        BinaryTree tmp = this;
        // 1表示添加到左节点，２表示添加到右节点
        int k = 1;
        // 遍历处理
        for (int i = 1; i < charArray.length; i++) {
            // 碰到左括号就将括号前的节点存入栈中作为后续操作的根节点
            // A(B(C,),D) 当第一次碰到（ 时将Ａ存入作为后续操作的根节点，并将ｋ变成１以待添加到左节点
            if (charArray[i] == '(') {
                stack.push(tmp);
                k = 1;
                // 右括号表示该根节点操作完毕 直接ｐｏｐ出来
            } else if (charArray[i] == ')') {
                stack.pop();
                // 逗号表示要添加到右节点
            } else if (charArray[i] == ',') {
                k = 2;
            } else {
                // 表示碰到了要添加的节点
                tmp = stack.peek();
                if (k == 1) {
                    BinaryTree left = new BinaryTree(charArray[i]);
                    tmp.lTree = left;
                    tmp = left;
                } else {
                    BinaryTree right = new BinaryTree(charArray[i]);
                    tmp.rTree = right;
                    tmp = right;
                }
            }
        }
    }

    /**
     * 构建单个树节点的构造方法
     * 
     * @param value 节点值
     */
    public BinaryTree(char value) {
        data = value;
        lTree = null;
        rTree = null;
    }

    /**
     * 默认构造函数
     */
    public BinaryTree() {
    }

    /**
     * 在二叉树中查找值为x的节点，返回节点的指针
     * 
     * @param c 查询的节点的值
     * @return 查询到的节点树, 不存在则返回null
     */
    public BinaryTree findNode(char c) {
        if (data == c) {
            return this;
        } else {
            if (this.lTree != null) {
                BinaryTree left = this.lTree.findNode(c);
                if (left != null) {
                    return left;
                }
            }
            if (this.rTree != null) {
                BinaryTree right = this.rTree.findNode(c);
                if (right != null) {
                    return right;
                }
            }
            return null;
        }
    }

    /**
     * 求二叉树的高度
     * 
     * @return 高度
     */
    public int binaryHeight() {
        if (this.data == '\u0000') {
            return 0;
        } else {
            int height1 = 1;
            int height2 = 1;
            if (this.lTree != null) {
                height1 += this.lTree.binaryHeight();
            }
            if (this.rTree != null) {
                height2 += this.rTree.binaryHeight();
            }
            return height1 > height2 ? height1 : height2;
        }
    }

    /**
     * 计算二叉树节点总数
     * 
     * @return 二叉树节点总数
     */
    public int nodesCount() {
        if (this.data == '\u0000') {
            return 0;
        } else {
            return 1 + (this.lTree == null ? 0 : this.lTree.nodesCount())
                    + (this.rTree == null ? 0 : this.rTree.nodesCount());
        }
    }

    /**
     * 计算二叉树叶子节点个数
     * 
     * @return 二叉树叶子节点个数
     */
    public int leafNodesCount() {
        if (this.data == '\u0000') {
            return 0;
        } else {
            int count = 0;
            if (this.lTree == null && this.rTree == null) {
                count = 1;
            } else {
                if (this.lTree != null) {
                    count += this.lTree.leafNodesCount();
                }
                if (this.rTree != null) {
                    count += this.rTree.leafNodesCount();
                }
            }
            return count;
        }
    }

    /**
     * 非叶子节点的个数
     * 
     * @return
     */
    public int notLeafNodesCount() {
        if (this.data == '\u0000') {
            return 0;
        } else {
            int count = 0;
            if (this.lTree != null) {
                count += this.lTree.notLeafNodesCount() + 1;
            }
            if (this.rTree != null) {
                if (this.lTree != null) {
                    count += this.rTree.notLeafNodesCount();
                }else{
                    count += this.rTree.notLeafNodesCount() + 1;
                }
            }
            return count;
        }

    }

    /**
     * 查找二叉树中值为x的节点的层次
     * @return
     */
    public int findNodeLevel(char c){
        if (data == c){
            return 1;
        }else{
            if (this.lTree != null){
                int level = this.lTree.findNodeLevel(c);
                if (level != -1){
                    return level + 1;
                }
            }
            if (this.rTree != null){
                int level = this.rTree.findNodeLevel(c);
                if (level != -1){
                    return level + 1;
                }
            }
        }
        return -1;
    }

    /**
     * 统计二叉树中第k层节点的个数n
     * @return 二叉树中第k层节点的个数n
     */
    public int KLevelNodesCount(int k){
        if (data == '\u0000'){
            return 0;
        }else{
            if (k == 1){
                return 1;
            }else{
                int count = 0;
                if (this.lTree != null){
                    count += this.lTree.KLevelNodesCount(k-1);
                }
                if (this.rTree != null){
                    count += this.rTree.KLevelNodesCount(k-1);
                }
                return count;
            }
        }
    }

    /**
     * 重构后的输出函数
     */
    @Override
    public String toString() {
        StringBuilder returnValue = new StringBuilder();
        returnValue.append(data);
        if (lTree != null) {
            returnValue.append("(");
            returnValue.append(lTree.toString());
            if (rTree != null) {
                returnValue.append(",");
                returnValue.append(rTree.toString());
                returnValue.append(")");

            } else {
                returnValue.append(",)");
            }

        } else {
            if (rTree != null) {
                returnValue.append("(,");
                returnValue.append(rTree.toString());
                returnValue.append(")");
            }

        }
        return returnValue.toString();
    }

    public char getData() {
        return data;
    }

    public void setData(char data) {
        this.data = data;
    }

    public BinaryTree getlTree() {
        return lTree;
    }

    public void setlTree(BinaryTree lTree) {
        this.lTree = lTree;
    }

    public BinaryTree getrTree() {
        return rTree;
    }

    public void setrTree(BinaryTree rTree) {
        this.rTree = rTree;
    }

}